package 二叉树练习题;

public class D如何求一棵二叉树的最大子树和 {
    /**
     * 给定一棵二叉树，它的每个结点都是正整数或负整数，
     * 如何找到一棵子树，使得它所有结点的和最大
     */

    public static int manSum = Integer.MIN_VALUE;

    /**
     *
     */
    public static int findMaxSubTree(BiTNode root, BiTNode maxRoot) {
        if (root == null) {
            return 0;
        }
        int lmax = findMaxSubTree(root.lchild, maxRoot);
        int rmax = findMaxSubTree(root.rchild, maxRoot);
        int sum = lmax + rmax + root.data;
        if (sum > manSum) {
            manSum = sum;
            maxRoot.data = root.data;
        }
        return sum;
    }

    public static BiTNode constructTree() {
        BiTNode root = new BiTNode();
        BiTNode node1 = new BiTNode();
        BiTNode node = new BiTNode();
        BiTNode node2 = new BiTNode();
        BiTNode node3 = new BiTNode();
        BiTNode node4 = new BiTNode();

        root.data = 6;
        node1.data = 3;
        node2.data = -7;
        node3.data = -1;
        node4.data = 9;

        root.lchild = node1;
        root.rchild = node2;
        node1.lchild = node3;
        node1.rchild = node4;
        node2.lchild = node2.rchild = node3.lchild = node3.rchild = node4.lchild = node4.rchild = null;
        return root;
    }


    public static void main(String[] args) {
        BiTNode root = constructTree();
        BiTNode maxRoot = new BiTNode();
        findMaxSubTree(root, maxRoot);
        System.out.println("最大子树和为：" + manSum);
        System.out.println("对应子树的跟节点为：" + maxRoot.data);
    }
}
